package Solutions

import "sort"

func combinationSum4(nums []int, target int) int {
	var dp = make([]int, target+1)
	dp[0] = 0
	if target == 0 {
		return 1
	}
	sort.Ints(nums)
	for i := 0; i < len(nums); i++ {
		if nums[i] > target {
			break
		}
		dp[nums[i]] = 1
	}
	for i := 1; i < len(dp); i++ {
		t := dp[i]
		for j := 0; j < len(nums); j++ {
			if i-nums[j] < 0 {
				break
			}
			t += dp[i-nums[j]]
		}
		dp[i] = t
	}
	return dp[len(dp)-1]
}
